package com.ruima.study.arithmetic.sortdemo;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * <p>
 * <p>求数组中第k大的数</p>
 * <p>
 * <p>Copyright (c) 2024/11/14 10:34, 科大讯飞 All Rights Reserve</p>
 *
 * @author ruima6
 * @version [V1.0]
 */
public class TopDemo {

    public static void main(String[] args) {
        int[] arr = {40, 30, 10, 20, 70, 60, 50};
        int result = -1;
        result = calK(arr,7);
        System.out.println(result);
    }

    public static int calK(int[] arr, int k) {
        int partition = partition(arr);
        if (partition == k) {
            return arr[partition - 1];
        } else if (partition > k) {
            arr = IntStream.of(arr)
                    .limit(partition)
                    .toArray();
            return calK(arr, k);
        } else {
            arr = Arrays.copyOfRange(arr, partition, arr.length);
            return calK(arr, k - partition);
        }
    }

    public static int partition(int[] arr) {
        int value = arr[arr.length - 1];

        int i = 0;
        int j = arr.length - 2;

        while (i <= j) {
            if (arr[i] > value && arr[j] > value) {
                i++;
                continue;
            } else if (arr[i] < value && arr[j] < value) {
                j--;
                continue;
            } else if (arr[i] < value && arr[j] > value) {
                swap(arr, i, j);
            }
            i++;
            j--;
        }
        for (int k = arr.length - 1; k > i; k--) {
            arr[k] = arr[k - 1];
        }
        arr[i] = value;
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }




}
